/* 

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。

如果存在则返回 true，不存在返回 false。

 

示例 1:

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
// 双循环，注意循环中利用题目所给的条件
var containsNearbyAlmostDuplicate = function (nums, k, t) {
    const len = nums.length;
    if (len < 2) {
        return false;
    }

    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j <= i + k && j < len; j++) {
            if (Math.abs(nums[i] - nums[j]) <= t) {
                return true;
            }
        }
    }
    
    return false;
};

// 桶解法
// 题解：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/
var containsNearbyAlmostDuplicate = function (nums, k, t) {
    // 解决js中 -0 === 0 为true的问题
    function getId(x, w) {
        return Math.floor(x / w)
    }
    if (t < 0) return false
    const map = new Map()
    const w = t + 1
    for (let i = 0; i < nums.length; i++) {
        const m = getId(nums[i], w)
        if (map.has(m)) return true
        else if (map.has(m + 1) && Math.abs(map.get(m + 1) - nums[i]) < w) return true
        else if (map.has(m - 1) && Math.abs(map.get(m - 1) - nums[i]) < w) return true
        map.set(m, nums[i])
        if (i >= k) map.delete(getId(nums[i - k], w))
    }
    return false
};